1. Field of the Invention
This invention relates to route determination and, in particular, to a method and device for determining a route, e.g., on a road network, based on estimation function values.
2. Related Art
Finding a good, preferably optimum, route from a given starting point to a given destination is one of the key features of car navigation systems or other systems providing routing information. Throughout this specification, the term “optimum route” is used for a least-cost route, the costs of a route being determined by the sum of costs of edges and vertices of a graph traversed by the route. For example, when a route is determined in a road network, the costs of the route correspond to the costs of the road segments traversed plus the costs associated with road segment junctions. Depending on the cost model employed, the costs may reflect distances, travel times and/or user preferences. Similarly, terms such as “good route” refer to routes that are associated with small costs, i.e., the quality of a route is measured with reference to the costs accrued upon traversal of the route. For a given graph defined by a set of edges and a set of vertices at which graph edges interconnect, various cost models may be defined. For example, in navigation systems, different cost models may correspond to different optimization criteria, such as fastest route, shortest route, avoiding tunnels, avoiding highways, avoiding ferries, avoiding toll roads or similar, and combinations of these options and preferences.
Several standard algorithms for finding an optimum route or a good route on a graph are known in the art, the most famous of which are Dijkstra's algorithm and the A*-algorithm. In Dijkstra's algorithm, the road network, or more generally, a graph is explored starting from the starting point of the route by edge relaxation or expansion, the different vertices of the road network being visited in order of minimum costs associated with a route connecting the vertex and the starting point. When the destination is reached in the expansion of graph edges, an optimum route from the starting point to the destination has been found, and Dijkstra's algorithm terminates.
The A*-algorithm is a modification of Dijkstra's algorithm that employs an estimation function for vertices of the graph. The estimation function for a given vertex provides an estimate for costs associated with an optimum route connecting the given vertex and the destination. In the route search, different paths are ranked according to a priority which is given by the sum of the costs accrued from the starting point to the vertex so far, and the estimation function value for the vertex. If the estimation function is such that it never overestimates costs of an optimum route connecting a vertex and the destination, the A*-algorithm is known to find a correct solution to the optimum path problem. Conventionally, the estimation function is determined based on simple geometrical criteria, such as an air distance.
Frequently, the route search for car navigation is performed on a dual graph of the road network, in which vertices of the dual graph represent road segments of the road network, to accommodate turning restrictions. In many applications, a route search is nowadays expected to provide added convenience features, such as determining several alternative routes, accommodating user preferences, dynamical routing, or similar. Both the usage of the dual graph to perform the route search and the above-mentioned additional features are costly in view of storage space requirements and computational time.
Therefore, a need exists in the art for improved system for determining routes that allow the complexity of the route search to be decreased. In particular, a need exists in the art for improved systems for determining routes that have moderate storage space and/or computational time requirements.